# ZJU 八月集训随记 * Day1 - SWERC 2017 - 2018.8.9 - Codeforces * Day2 - GCPC 2010 - 2018.8.10 - vjudge * Day3 - NEERC Moscow 2017 - 2018.8.11 - Codeforces * Day4 - 2013 Andrew Stankevich Contest 43 - 2018.8.12 - opentrains * Day4.5 - Makoto Soejima Contest 3 (MIPT Workshop Open 2) - 2018.8.13 - opentrains * Day5 - 2018 Multi-University Training Contest 7 - 2018.8.14 - vjudge * Day6 - NEERC Northern Subregional Contest St Petersburg 2017 - 2018.8.15 - Codeforces * Day 7 - CERC 2017 - 2018.8.16 - Codeforces * Day 8 - JAG Autumn 2014, MIPT2014 Round 1 - 2018.8.17 - opentrains * Day 9 - NEERC 2014 - 2018.8.18 - opentrains * Day 9.5 - XVIII Open Cup named after E.V. Pankratiev. GP of Urals - 2018.8.19 - opentrains * ...... 全程为 ACM 赛制组队训练，小数天数指队伍加训。**Xnyttt** 表示在时间 $ttt$ 的时候提交了题目 X 的第 $n$ 份代码并获得 AC。 队友：郑鸿鹄（Codeforces@zhhhplus）、林思仪（Codeforces@LIN452） ## Day1 - SWERC 2017 - 2018.8.9 - Codeforces ### 赛时流水账 开场读题并未发现签到题，看了一下榜发现 F 有人过，向 lsy 读了一下发现是傻逼题，于是 **F1y18** ，之后 zhh **A1y35**，在 zhh 写题期间看到 J 也有人过，发现写一个前缀和就好了，于是 **J1y40**，之后 zhh 敲完了计算几何的板子，并写了 K 题，但一直 WA on 18，打印出来后发现把点到直线的距离写成了点到线段距离，改了之后 **K4y121** ，期间我一直在想 C 的 DP 但发现会 TLE，zhh A 完 K 后也得出了 $3^8 \times 3^8$ 的矩阵，最终未能得到正解。期间 lsy 觉得 D 能写，我则和 zhh 讨论 G，发现可以建图跑费用流，我抄了自己的板子但是 TLE 了，而 KM 算法感觉也不能过，于是一直让 lsy 去写 D。我读了一下 E 题，虽然没看懂样例，但感觉可以先拓扑排序在背包，但由于理解错了题意，写了完全背包，而正解是 01 背包，导致连样例都过不了。最后几十分钟时，zhh 打算抄一遍 KM 的板子写 G，但写完后发现不会用，同时也到点了。最终 4 题，rk11。 ### 赛后 E 改了一下就 A 了。C 得知可以用斐波那契数列优化成 $2^8 \times 2^8$ 的矩阵就可以做了。lsy 之后也补掉了 B 题。 ## Day2 - GCPC 2010 - 2018.8.10 - vjudge ### 赛时流水账 开场读题并未发现签到题，看榜发现了 H 题，差分三次即可，但是有一点细节写错了 WA 了两发，最终 **H3y21**。A 完 H 看榜发现 I 也是签到题，于是 zhh **I1y35**，lsy 觉得 D 是 Tarjan 也能做，于是 **D2y98**，期间和 zhh 讨论了一下 A，我想了想细节发现十分好写，于是 **A1y89**。我给 lsy 与 zhh 说了 G 的题意后，二人给出了不同的解法，其中 zhh 的做法听起来不太对，但是好写，于是 WA 了三发后交由 lsy 写状压，由于未清空数组，又 WA 了三发后 **G7y147**，期间给 zhh 说了一下 C 的题意后发现写个拓扑排序即可，但由于开小了数组，**C2y124** 。在 lsy 调 G 的时候，zhh 给我讲了 J 的题意和做法，感觉十分的正确，但当时还没有人 AC J 题，zhh 先敲了板子，在 lsy 过了 G 后 **J1y182**。期间 lsy 读了 E 题，zhh 听后感到奇怪，交由我确认了一下题意，感觉可以 sam，于是 lsy 去看板子回忆 sam。我读了 K 的题面后感觉是个傻逼题，但一直 WA 到比赛结束，lsy 的 sam 也没有调出来。最终 7 题，rk 12。 ### 赛后 K 发现是全队三人不认识 perpendicular，导致细节出错，改了之后 A 了。E sam 确实能做，但标算似乎是 trie，另外，用 `std::set` 的暴力也可以过。 ## Day3 - 2018.8.11 - NEERC Moscow 2017 - Codeforces ### 赛时流水账 开场我因为少读了 E 的一个条件，WA 了一发（E 题全场唯一的一发提交）。之后 lsy 发现 D 可以签到，由于爆 `long long` WA 了一发，**D2y63**，之后 zhh **A2y68**。zhh 给我说了一下 H 的题意发现可写但细节比较多，我去推了推式子但是 WA 了三发，未能找到错误。期间 zhh 写 F 的模拟到心态爆炸，换了 lsy 去写 F，同时 lsy 告诉了 zhh C 的做法，最后 lsy **F3y208**。zhh 发现lsy 的 C 有问题，打算用树剖，于是告诉我了题意，因一些细节问题又 WA 了几发，最后 **C7y266** 。lsy 看了一下我的 H 的代码，不过还是重写了一遍 H 后 **H4y282**，最后十几分钟和 zhh 读了 G，随便写了一下果然 WA 了。最终 5 题，rk 12。 ### 赛后 发现自己的 H 把一个减号写成了加号；G 发现是个很简单的题但由于卡题而没有去读。 ## Day4 - 2013 Andrew Stankevich Contest 43 - 2018.8.12 - opentrains ### 赛时流水账 开场和 lsy 交换了一下 B 的思路，我找了一下规律，得到了一个细节有点问题的做法，lsy 补充后 **B1y98**，之后 zhh 和 lsy 讨论了一下 I，于是 lsy **I1y147**。和 zhh 讨论了一下 H 后发现可以构建最小割模型，但一直 WA on 14。同时 zhh 告诉我了 K 的题意和做法，由于理解出了偏差，WA 了几发，最后 **K5y258**。期间 zhh 与 lsy 一直尝试构造 J 但是失败。最后 zhh 说了一下 L 可能 的解法，我写了一发但是 WA 了。最终 3 题，rk 10。 ### 赛后 H 题把我们的拆点做法改为不拆点就能 A，但是对排了一百多组随机数据也没能找到拆点做法的错误。我在听了 J 的题意后便想到了标算的构造，到当时感觉有问题而没说，zhh 和 lsy 也没能想出这个构造（这个锅我背了。。。），L 发现 zhh 给的做法有一点问题。 ## Day4.5 - Makoto Soejima Contest 3 (MIPT Workshop Open 2) - 2018.8.13 - opentrains ### 赛时流水账 开场先和 zhh 想了 E 和 H，去机子上打了 E 的表，zhh 则打开 OEIS 书但是未能找到。lsy 发现 B 是个贪心，于是 **B3y41**。给 zhh 和 lsy 说了 C 的题意，自己则在打 H 的表，zhh 以为发现了规律，但多打了一些后发现是错的，不过我有了一个思路，但复杂度不对。lsy **C2y121** 后听了我的 H 的思路开始和 zhh 一起思考，同时给我说了 G 可以大力讨论，讨论了一下后我感觉能写，WA 了几发后发现了一个大 bug，lsy 提出了想法，但由于我理解处理偏差，半个小时后才意识到是对的，修完 bug 后还是 WA，并且还是想不到 WA 点，H 题那边 lsy 想到了做法，但感觉会 TLE 而没有写。最终 2 题。 ### 赛后 赛后发现自己的 G 用到了可能未被算出来的数据，改了一下后 AC 了；lsy 的 H 题做法其实的对的。我学习了一下「竞赛图的强连通分量数等于划分成两个非空点集 $S$、$T$ 使得二者之间的边都是由 $S$ 指向 $T$ 的方案数加一」的姿势并补掉了 E，同时补掉了另一个计数题 D。 ## Day5 - 2018 Multi-University Training Contest 7 - 2018.8.14 - vjudge ### 赛时流水账 开场我先看了 E、F 和 H，感觉 E 可以做，稍微找了找规律，发现是完全积性的，同时回忆了一下某个经典式子的反演结果（懒地推了），敲完后发现样例过不了，又看了看发现只是普通的积性，改完后 TLE，删除了几次多余的取模操作后 **E2y99**，拿下 E 的一血。之后 zhh 给我说了 J 的题意，发现是傻逼签到题，写完后 **J1y118**。zhh 和 lsy 讨论了A，lsy 去写了，但是 TLE。zhh 卡了卡常后，lsy 发现了一处问题，修改后本地十组大数据 $3$s，时限 $2.5$s 且原题有二十组数据，但还是交了一发，**A3y201**。zhh 告诉我 H 可以树剖，I 可以 LCT，想了想确实都是板子题，考虑到我的 LCT 可能不是很好调 + LCT 的常数比较大，我选择去写 H，但是一直 WA。同时 lsy 想到了 K 的做法，也没有调出来。最终 3 题，rk 8。 ### 赛后 H 发现一个细节写错了：二次修改一个点时我找的是初始值而非之前修改后的值，改了之后 AC，但实际上 H 有更短更好写的做法。lsy 调完了自己的 K 也 AC 了。之后用自己的 LCT 板子过了 I 发现并不用担心常数。 ## Day6 - NEERC Northern Subregional Contest St Petersburg 2017 - 2018.8.15 - Codeforces ### 赛时流水账 开场 lsy **A1y12**，zhh 想到了 L 的做法并去写，但死机了，之后 lsy **B1y44**，期间我发现 I 很可写，K 也是个傻逼构造，于是 **K1y53**，lsy 先写了一发 C，于是 **C1y75**，我想完 I 的细节，**I1y93**。十分钟后过了 L 的样例，但是 WA on 6，发现问题后又 WA on 13。lsy 和 zhh 想到了 E 的做法，但是 RE on 4 和 WA on 8。我又意识到了 L 可能会发生 `long long` 与 `double` 间的精度问题，改了一发 WA on 29，又想到一点后 **L4y169**。lsy 与 zhh 发现 E 做法的问题，zhh 改正后 **E5y212**。之后 zhh 想到了 G 的做法，我和 lsy 也思考了一下 H，感觉做出 G 的概率更大，于是我去写了 G 的点双，写了各种细节后 RE on 2。最终 7 题，rk 7。 ### 赛后 G 发现问题后不断地 WA on 2（有 $1815$ 个子测试点），但其实有更简单的做法，lsy 补掉了 G。同时我和 lsy 补掉了 H。 ## Day 7 - CERC 2017 - 2018.8.16 - Codeforces ### 赛时流水账 开场先 WA 了三发 F，而且是 WA on 1，但是本地确实过了样例，期间修正了一些细节，我怀疑是多组数据或 PE，zhh 表示了否定，F 先放下了。之后 lsy **A1y80**，zhh 和我说了一下 J 的题意，发现很可写，于是 **J1y85**。之后 zhh 重写了 F，仍然 WA on 1，lsy 表示用 `%lld` 输出 `int` 可能会有问题，zhh 改了后 **F6y114**。我跟榜去看了 H，看了两遍后看懂了题意，发现直接建树跑 dfs 即可，于是 **H1y133**。这时发现总榜上只有 G、K 和 L 有人过，过 G 的人更多，于是 zhh 和 lsy 去想 G，不擅长期望的我准备开别的题。一段时间后，看到 EuropeSun（oyyf、wyh、zx）过了 L，于是去看 L，看到坐标范围很小，感觉可以差分，思考了一段时间细节。期间 lsy 想到了 G 的转移，在因为写错一个括号的位置 WA 了一发后 **G2y228**。之后我去写 L，调了一段时间细节后发现交不上去，五六分钟后 MLE on 1（算了一下只超了 $4$M），删去一个无用数组后 WA on 1，发现是修改时没有修改完，最后 **L3y282**，最后读了一下 D 的题意放弃。最终 6 题，rk 5。 ### 赛后 自已的 F 改掉 `%lld` 也过了。 ## Day 8 - JAG Autumn 2014, MIPT2014 Round 1 - 2018.8.17 - opentrains ### 赛时流水账 开场跟榜知道 A 是签到题，但理解了二十分钟，写完后 WA on 1，和 zhh 浪费了二十分钟找错，最后发现是交成了 13 号的 A 题，于是 **A2y49**。之后 lsy 与 zhh 讨论出来 G，因为未初始化 + 爆了 `long long` WA 了两发，**G3y96**。期间 zhh 给我讲了 B 的高斯消元做法，我去一旁回想高消，同时 zhh 去和 lsy 讨论 D。D 在 WA 了一次后 **D2y223**，我在期间写完了 B 并开始调试，一段时间后过了样例，但是 WA on 2，zhh 指出从上三角消成对角线时的错误，仍然 WA on 2，最后 zhh 意识到最后可能还是消不成对角线并且我会 WA 在这个地方，改正后 **B6y265**。最后写了些中途看的 K 题，一直过不了样例。最终 4 题，rk 12。 ### 赛后 zhh 指出了一个问题，K 在赛后几秒过了样例，但是 TLE，改正几发后补掉了。同时发现 H 是个傻逼题，但是没有人读了题面，赛后十几分钟后一遍过掉了。网络流的 F 和 DP 的 J 则被 lsy 补了。 ## Day 9 - NEERC 2014 - 2018.8.18 - opentrains ### 赛时流水账 开场 zhh 快速 **A1y13**，之后我暴力 **K1y23**，再之后 lsy 爆搜 **J2y48**。之后我发现 F 暴力的复杂度是对的，但是 WA 了两发，期间 zhh 与 lsy 讨论出了 B，于是 zhh **B1y86**。之后我发现我的 F 是因为把 `j` 打成了 `i`，改正后 **F4y110**。再之后 lsy 发现了 I 的性质，于是 **I1y150**。后半场 zhh 与 lsy 在思考 E，我则在想了一会儿 E 后转去想 D，突然想到了祖暅原理，觉得可以暴力微分，zhh 则提出了蒙特卡洛，但无论是哪个，推了好久式子都没能推出来；zhh 想到了 E 的做法，但由于细节比较难写而没有写出。最终 6 题，rk 5。 ### 赛后 赛后理清了思路写了 D 题，调了几个小时后过了样例一，但是 WA 样例二，又过了几个小时发现是打错了变量名（一天两次……），最后由于精度 WA on 48 一次过了。 ## Day 9.5 - XVIII Open Cup named after E.V. Pankratiev. GP of Urals - 2018.8.19 - opentrains ### 赛时流水账 开场发现 B 是签到，三人讨论了一下后 WA on 2，再次讨论后补上一个细节后 **B2y53**。之后一个多小时思考 A 和 C，但是毫无进展。lsy 想到了 K 的做法，写好后 WA on 4，改正一些后 WA on 7，此时还剩半场的时间，而 lsy 的代码看起来比较正确，在更改了感觉更正确的写法后仍然 WA on 7，zhh 提议面向评测机调试，但返回的结果却是最难调的情况。我仔细查过 lsy 的代码后，感觉正确无比，但是 WA on 7。期间我思考了一下 D，转化为若干个 $[0, 9]$ 的数和为某个数的方案数，但式子推不出来。最终 1 题。 ### 赛后 lsy 用 K 的标程对拍，随机了几百组数据没有拍出错误。D 在容斥时钦定超过即为 $10$ 就是对的。